package main

import (
	"container/list"
	"fmt"
)

/*
从上到下打印二叉树 II
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
例如:
给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：
[
  [3],
  [9,20],
  [15,7]
]
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

//不借助队列
/*
func levelOrder(root *TreeNode) [][]int {
    var res = make([][]int,0)
    var helper func(root *TreeNode, level int)
    helper = func(root *TreeNode,  level int){
    if root == nil {
        return
    }
    if len(res) <= level{
        (res) = append((res), []int{})
    }
    (res)[level] = append((res)[level], root.Val)
    helper(root.Left,  level+1)
    helper(root.Right,  level+1)
    }
    helper(root, 0)
    return res
}
*/

//借助队列
func levelOrder(root *TreeNode) [][]int {
	var res [][]int
	if root == nil { //防止为空
		return res
	}
	queue := list.New()
	queue.PushBack(root)
	var tmpArr []int
	for queue.Len() > 0 {
		length := queue.Len() //保存当前层的长度，然后处理当前层（十分重要，防止添加下层元素影响判断层中元素的个数）
		for i := 0; i < length; i++ {
			node := queue.Remove(queue.Front()).(*TreeNode) //出队列
			if node.Left != nil {
				queue.PushBack(node.Left)
			}
			if node.Right != nil {
				queue.PushBack(node.Right)
			}
			tmpArr = append(tmpArr, node.Val) //将值加入本层切片中
		}
		res = append(res, tmpArr) //放入结果集
		tmpArr = []int{}          //清空层的数据
	}
	return res
}

func main() {
	t := &TreeNode{Val: 1}
	t.Left = &TreeNode{Val: 2}
	t.Right = &TreeNode{Val: 3}
	t.Left.Left = &TreeNode{Val: 4}
	t.Left.Right = &TreeNode{Val: 5}
	t.Right.Left = &TreeNode{Val: 6}
	/*树的形状
	       1
	    /     \
	   2       3
	  / \     /
	 4   5   6             */
	fmt.Println("层次排序:")
	fmt.Println(levelOrder(t))

}
